package com.hfb.mashibing.alip8.diamondsquarealgorithm.class05;

/**
 * 算法：马拉车算法应用
 * 题目
 *      随意给定一个字符串，求必须在该字符串后面依次添加哪些字符，使得整体是回文字符串。
 *
 * 题目实质
 *      必须包含源字符串最后一个字符的情况下，最长回文子串是多长。
 *      然后把前面不是回文的字符串逆序加到后面就行了。
 *
 */
public class Code02_AddShortestEnd {
    public static char[] manacherString(String s) {
        char[] str = s.toCharArray();
        char[] res = new char[2 * str.length + 1];
        int index = 0;
        for (int i = 0; i != res.length; i++) {
            res[i] = (i & 1) == 0 ? '#' : str[index++];
        }
        return res;
    }

    public static String shortestString(String s) {
        if (s == null || s.length() == 0) {
            return null;
        }
        char[] str = manacherString(s);
        int[] pArr = new int[str.length];
        int C = -1;
        int R = -1;
        int maxContainsEnd = -1;
        for (int i = 0; i < str.length; i++) {
            pArr[i] = R > i ? Math.min(pArr[2 * C - i], R - i) : 1;
            while (i + pArr[i] < str.length && i - pArr[i] > -1) {
                if (str[i + pArr[i]] == str[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = R;
            }
            if (R == str.length) {
                maxContainsEnd = pArr[i];
                break;
            }
        }
        char[] res = new char[s.length() - maxContainsEnd + 1];
        for (int i = 0; i < res.length; i++) {
            res[res.length - 1 - i] = str[2 * i + 1];
        }
        return String.valueOf(res);
    }

    public static void main(String[] args) {
        String str1 = "abcd123321";
        System.out.println(shortestString(str1));
    }

}
